home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / othdbm.c < prev    next >
Text File  |  1989-05-23  |  19KB  |  637 lines
  1. /*-----------------------------------------------------------------------------
  2. OTHDBM.C
  3.  
  4. Revision History
  5. ----------------
  6. Jon Ward    17 Oct 1988    Initial Revision.
  7. Jon Ward    30 Oct 1988    Mods for move type.
  8. Jon Ward    30 Oct 1988    Optimized and combined the allocate functions.
  9.                   Now we use the macros ALLOCATE_LIMB and
  10.                   ALLOCATE_BOARD.
  11. Jon Ward    04 Dec 1988    Debugging commencing.
  12. Jon Ward    03 Jan 1989    Added relinking ability to db_delete_subtree
  13.                   changed free_limb from static to global.
  14. -----------------------------------------------------------------------------*/
  15.  
  16. #include <string.h>
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <malloc.h>
  20.  
  21. #include "othello.h"
  22.  
  23.  
  24. /*-----------------------------------------------------------------------------
  25. How This Thing Works:
  26. There will be two data spaces. One for limbs, and one for boards. Each data
  27. space will be maintained as an array. Each array will be bit-mapped so that
  28. we can determine if an element in the array is unused.
  29. -----------------------------------------------------------------------------*/
  30.  
  31. /*------------------------------------------------
  32. The following structure bd_row_st is used as a
  33. trick to get the MSC compiler to perform a struct
  34. assignment for the board row. The reason for this
  35. is that the database boards are stored in a far
  36. area of ram. Segmentation...Argh!!!!
  37.  
  38. The dbm_board_st struct is a compressed form of
  39. the board_st structure used every else in the
  40. program. The boards, when compressed, are much
  41. smaller, about 52% smaller or 66% as big as they
  42. would have been.
  43. ------------------------------------------------*/
  44.  
  45. struct bd_row_st
  46.   {
  47.   unsigned char row [8];
  48.   };
  49.  
  50. struct dbm_board_st
  51.   {
  52.   struct bd_row_st board [8];
  53.   unsigned char fa_bits [FA_BITS_SIZE];
  54.   };
  55.  
  56. typedef struct dbm_board_st dbm_board_type;
  57.  
  58.  
  59. #define MAX_DBM_LIMBS  65536 / sizeof (limb_type)
  60. #define MAX_DBM_BOARDS 32768
  61.  
  62. STATIC limb_type far limb_array [MAX_DBM_LIMBS];
  63.  
  64. STATIC key_type num_limbs_left;        /* number of limbs available */
  65. STATIC key_type num_boards_left;    /* number of boards available */
  66.  
  67. #define MAX_BD_PTRS        50
  68. #define STORED_BOARD_SIZE    sizeof (dbm_board_type)
  69.  
  70. STATIC key_type bd_per_blk = 16384 / STORED_BOARD_SIZE;
  71. STATIC dbm_board_type far *board_ptrs [MAX_BD_PTRS];
  72. STATIC int bd_blks;
  73.  
  74. typedef unsigned int am_type;        /* availability map type */
  75. #define AM_SIZE (8 * sizeof (am_type))    /* bits in availability map type */
  76.  
  77. STATIC am_type lam [(MAX_DBM_LIMBS + 7) / 8];    /* limb availability map */
  78. STATIC am_type bam [(MAX_DBM_BOARDS + 7) / 8];    /* board availability map */
  79.  
  80. #define AM_USED ((am_type) (-1))
  81.  
  82. #define LAM_SIZE (sizeof (lam) / sizeof (lam [0]))
  83. #define BAM_SIZE (sizeof (bam) / sizeof (bam [0]))
  84.  
  85.  
  86. /*-----------------------------------------------
  87. The following macros are used to GET, SET, and
  88. CLR bits in the limb and board availability maps.
  89. -----------------------------------------------*/
  90.  
  91. #define GET_BIT(x,y) (((x) [(y) / AM_SIZE]) &   (1 << ((y) % AM_SIZE)))
  92. #define SET_BIT(x,y) (((x) [(y) / AM_SIZE]) |=  (1 << ((y) % AM_SIZE)))
  93. #define CLR_BIT(x,y) (((x) [(y) / AM_SIZE]) &= ~(1 << ((y) % AM_SIZE)))
  94.  
  95.  
  96. key_type max_limb_key = MAX_DBM_LIMBS;        /* maximum key number for limbs */
  97. key_type max_board_key = MAX_DBM_BOARDS;    /* maximum key number for boards */
  98.  
  99. key_type last_parent_key;    /* last parent child was added to */
  100. key_type last_child_key;    /* last child added */
  101.  
  102.  
  103. /*-----------------------------------------------------------------------------
  104.                          Local Function Prototypes
  105. -----------------------------------------------------------------------------*/
  106. STATIC key_type allocate_limb (int am_sel);
  107. STATIC void free_board (key_type board);
  108. STATIC void free_subtree (key_type key);
  109. STATIC void get_board (
  110.   key_type key,
  111.   board_type *board);
  112. STATIC void put_board (
  113.   key_type key,
  114.   board_type *board);
  115.  
  116.  
  117. /*-----------------------------------------------------------------------------
  118. The following data is used by the allocate_am function when searching for and
  119. allocating a limb or board element in the database.
  120. -----------------------------------------------------------------------------*/
  121.  
  122. struct am_struct
  123.   {
  124.   am_type *am;        /* pointer to availability map */
  125.   key_type size;    /* number of elements in availability map */
  126.   key_type *max;    /* maximum key for am */
  127.   int *num_avail;    /* number of available elements */
  128.   };
  129.  
  130.  
  131. STATIC struct am_struct am_data [] =
  132.   {
  133.     { lam, LAM_SIZE, &max_limb_key,  &num_limbs_left },
  134.     { bam, BAM_SIZE, &max_board_key, &num_boards_left },
  135.   };
  136.  
  137.  
  138. #define ALLOCATE_LIMB()  (allocate_am (0))
  139. #define ALLOCATE_BOARD() (allocate_am (1))
  140.  
  141.  
  142. /*-----------------------------------------------------------------------------
  143. STATIC key_type allocate_am (int am_sel);
  144.  
  145. This function will locate the next available element in either the limb or
  146. board array. The am_sel argument determines whether the limb (0) or board (1)
  147. map will be used. If a free element if found, it is marked as used, and the
  148. key for referencing that element is returned. If no free space is available,
  149. the NO_KEY manifest constant is returned to indicate an allocation failure.
  150. -----------------------------------------------------------------------------*/
  151.  
  152. STATIC key_type allocate_am (int am_sel)    /* availability map selector */
  153. {
  154. struct am_struct *amp;    /* pointer into availability map structure */
  155. register am_type *pt;    /* pointer into the limb availability map */
  156. register key_type key;    /* key var */
  157.  
  158.  
  159. amp = &am_data [am_sel];    /* init pointer to am struct */
  160.  
  161.  
  162. for (pt = amp->am; pt < (amp->am + amp->size); pt++)
  163.   {
  164.   if (*pt != AM_USED)                /* if a limb is free */
  165.     {
  166.     am_type am_entry;                /* var copy of am entry */
  167.  
  168.     key = AM_SIZE * (pt - amp->am);
  169.     am_entry = *pt;
  170.  
  171.     for (; am_entry & 1; am_entry >>= 1, key++);    /* generate the key */
  172.  
  173.     if (key >= *(amp->max))    /* range check the key */
  174.       break;            /* break if it's too big */
  175.  
  176.     SET_BIT (amp->am, key);    /* set alloc bit if range ok */
  177.     *(amp->num_avail) -= 1;    /* decrement number available */
  178.  
  179.     return (key);        /* return the key */
  180.     }
  181.   }
  182.  
  183. return (NO_KEY);                /* out of limb space */
  184. }
  185.  
  186.  
  187. /*-----------------------------------------------------------------------------
  188. void free_limb (key_type limb);
  189.  
  190. This function will free the array element associated with a previously
  191. allocated limb. The limb argument id the index for the array element to free.
  192. The limb is freed merely by clearing the corresponding bit in the limb
  193. availability map.
  194. -----------------------------------------------------------------------------*/
  195.  
  196. void free_limb (key_type limb)
  197. {
  198. if (limb >= 0 && limb < max_limb_key && GET_BIT (lam, limb))
  199.   {
  200.   num_limbs_left++;
  201.   CLR_BIT (lam, limb);
  202.   }
  203. }
  204.  
  205.  
  206. /*-----------------------------------------------------------------------------
  207. STATIC void free_board (key_type board)
  208.  
  209. This function will free the array element associated with a previously
  210. allocated board. The board argument id the index for the array element to free.
  211. The board is freed merely by clearing the corresponding bit in the board
  212. availability map.
  213. -----------------------------------------------------------------------------*/
  214.  
  215. STATIC void free_board (key_type board)
  216. {
  217. if (board >= 0 && board < max_board_key && GET_BIT (bam, board))
  218.   {
  219.   num_boards_left++;
  220.   CLR_BIT (bam, board);
  221.   }
  222. }
  223.  
  224.  
  225.  
  226. /*-----------------------------------------------------------------------------
  227. void db_init (void);
  228.  
  229. This function will clear the othello database manager variables and prepare
  230. some data space for the othello program to use. It should only be called once
  231. to initialize the database.
  232.  
  233. Return Value
  234. None.
  235. -----------------------------------------------------------------------------*/
  236.  
  237. /*-----------------------------------------------
  238. The following pragma declares the memset function
  239. to generate inline code
  240. -----------------------------------------------*/
  241. #pragma intrinsic (memset)
  242.  
  243. void db_init ()
  244. {
  245. key_type blk_size;            /